[백준 알고리즘] 4949번: 균형잡힌 세상
June 03, 2021
문제
세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호(”()”) 와 대괄호(”[]“)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.
- 모든 왼쪽 소괄호(”(“)는 오른쪽 소괄호(”)“)와만 짝을 이뤄야 한다.
- 모든 왼쪽 대괄호(”[“)는 오른쪽 대괄호(”]“)와만 짝을 이뤄야 한다.
- 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
- 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
- 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.
풀이
모든 괄호문제가 그렇듯이 스택을 활용하면 큰 문제없이 해결할 수 있었다. 한 줄 씩 읽으면서 일반 문자는 다 무시하고 괄호가 나올 때마다 스택을 사용해서 짝이 맞으면 pop 해주고, 문자열의 모든 문자를 검사했을 때 스택이 비어있다면 균형이 맞는 괄호이므로 yes 스택에 남아있는 괄호가 있다면 균형이 안맞으므로 no를 출력한다.
코드
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main (){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
string line;
while(getline(cin, line)){
stack<char> bucket;
if (line.compare(".") == 0) break;
for (auto c : line){
if (!bucket.empty() && c == ')' && bucket.top() == '('){
bucket.pop();
}
else if (!bucket.empty() && c == ']' && bucket.top() == '['){
bucket.pop();
}
else if (c == '(' || c =='[' || c == ')' || c == ']'){
bucket.push(c);
}
}
if (bucket.empty()) cout << "yes\n";
else cout << "no\n";
}
}
